/*************************************
* 3、编写一个算法，对AOV网进行拓扑排序。*
* AOV网采用邻接矩阵存储。              *
**************************************/

#include<stdio.h>
#include<malloc.h>

typedef struct{int col,row;int* data;} mat;

void print_mat(const mat* m){
    int i,j;
    printf("<Matrix %dx%d>\n",m->row,m->col);
    for(i=0;i<m->col;i++){
        for(j=0;j<m->row;j++)printf("%d ",(m->data)[i*m->col+j]);
        putchar('\n');
    }
}

void print_topo_order(const mat* m){
    int* vis = malloc(sizeof(int)*m->row);
    int* order = malloc(sizeof(int)*m->row);
    int i,j,k,l;
    for(l=0;l<m->row;l++)vis[l]=0;
    for(k=0;k<m->row;k++){
        for(j=0;j<m->row;j++){
            if(vis[j])continue;
            l = 0;
            for(i=0;i<m->row;i++){
                if(vis[i])continue;
                l += m->data[i*m->col+j]; 
            }
            if(l == 0){
                vis[j] = k+1;
                order[k]=j+1;
                break;
            }
        }
    }
    for(l=0;l<m->row;l++)printf("%d ",order[l]);
    putchar('\n');
    free(vis);free(order);
}

int main(){
    // get adjacency matrix
    int i,j;
    printf("Enter verteice count: ");
    scanf("%d",&i);
    printf("Enter Matrix by rows:\n");
    mat A; A.row = i; A.col = i;
    A.data = malloc(sizeof(int)*A.row*A.col);
    for(i =0;i<A.row;i++){
        printf("Row #%d> ",i+1);
        for(j=0;j<A.col;j++){scanf("%d",A.data+i*A.col+j);}fflush(stdin);
    }
    printf("Get Adjacency matrix:\n");print_mat(&A);
    print_topo_order(&A);
    free(A.data);
}